package gpl.pierrick.brihaye.util;

import java.util.Collection;

/**
 * Builds a tree that has a character over each branch,
 * and tests a string if it has a path in this tree.
 * We add strings and check them in reverse order because
 * this is what we need from it.
 * @author Ahmed Saad
 */
@SuppressWarnings("unchecked")
public class TestTree {
	/**The root node of the TestTree.*/
	private TreeNode<?> root;
	
	/**
	 * Builds an empty tree
	 */
	public TestTree() {
		root = new TreeNode();
	}

	/**
	 * Adds the given String to the TestTree.
	 * It checks character one by one starting from the end,
	 * it adds nodes in the tree so that there is a path from the root with the given string
	 * @param s the string to be added
	 */
	public void add(String s) {
		TreeNode<?> p = root;
		for (int i=s.length()-1;i>=0;i--) {
			char c = s.charAt(i);
			TreeNode q = p.get(c);
			if (q==null) {
				q = new TreeNode();
				p.put(c,q);
			}
			p = q;
		}
	}
	
	/**
	 * Add all given strings to the tree using {link #add(String)}
	 * @param cs
	 */
	public void addAll(Collection<String> cs) {
		for (String s:cs)
			add(s);
	}
	
	/**
	 * Checks the given String in the TestTree.
	 * It checks character of the string one bye one starting from the rear.
	 * 
	 * @param s the string to be checked
	 */
	public boolean contains(String s) {
		TreeNode<?> p = root;
		int i=s.length();
		while (--i>=0) {
			//get next character
			char c = s.charAt(i);
			//get the child node under the next character
			TreeNode<?> q = p.get(c);
			//no branch with this character
			if (q==null)
				return false;
			//if this is a leaf node, we have finished
			if (q.isEmpty())
				return true;
			p=q;
		}
		
		return false;
	}
	
	public static void main(String args[]) {
		TestTree tt = new TestTree();
		tt.add("er");
		tt.add("or");
		tt.add("ion");
		tt.add("ed");
		
		System.err.println(tt.contains("ionor"));
	}
}